438. Find All Anagrams in a String

Similar Question

leading to the advanced question

Solution Tips

方案一: 滑动窗口

使用数组维护窗口特征, 但是本质上还是哈希表

var findAnagrams = function(s, p) {
    const sLen = s.length, pLen = p.length;

    if (sLen < pLen) {
        return [];
    }

    const ans = [];
    // 用数组, 方便比对两个 count 是否相等, 如果用哈希表就是另外写一个比对函数
    const sCount = new Array(26).fill(0);
    const pCount = new Array(26).fill(0);
    for (let i = 0; i < pLen; ++i) {
        ++sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++pCount[p[i].charCodeAt() - 'a'.charCodeAt()];
    }

    if (sCount.toString() === pCount.toString()) {
        ans.push(0);
    }

    for (let i = 0; i < sLen - pLen; ++i) {
        // 固定滑动窗口大小, 弹出一个更新结构, 加入一个更新结构
        --sCount[s[i].charCodeAt() - 'a'.charCodeAt()];
        ++sCount[s[i + pLen].charCodeAt() - 'a'.charCodeAt()];

        if (sCount.toString() === pCount.toString()) {
            ans.push(i + 1);
        }
    }

    return ans;
};

方法二: 使用单个 Count 结构

var findAnagrams = function(s, p) {
    const sLen = s.length, pLen = p.length;

    if (sLen < pLen) {
        return [];
    }

    const ans = [];
    // 只维护单个 count 数组
    const pCount = new Array(26).fill(0);
    for (let i = 0; i < pLen; ++i) {
        ++pCount[p[i].charCodeAt() - 'a'.charCodeAt()];
    }

    // a 总共的字符数
    let a = 0;
    // 抵消掉的字符数
    let b = 0;
    for (let i = 0; i < pCount.length; i++) {
        if (pCount[i] != 0) {
            a++
        }
    }
    let left = 0;
    let right = 0;
    while (right < s.length) {
        if (--pCount[s[right].charCodeAt() - 'a'.charCodeAt()] === 0) {
            // 用 right 位置的字符去抵消 p 的 count, 如果抵消后为 0
            // 说明此时子串 left right 中该字符的数量与 p 相等
            b++;
        }
        if (right - left + 1 <= p.length) {
            // 单词还没找够
        }
        else {
            // 窗口的大小已经超过 p 的长度了, 窗口左端点右移, count 恢复
            if (++pCount[s[left].charCodeAt() - 'a'.charCodeAt()] === 1) {
                // 恢复的词频为 1, 说明少了一个被抵消的字符
                b--
            }
            left++;
        }
        if (b === a) ans.push(left)
        right++;
    }

    return ans;
};

方法三: 滑动窗口 + Case 优化 跳跃更新窗口

var checkInclusion = function(s1, s2) {
    const n = s1.length, m = s2.length;
    if (n > m) {
        return false;
    }
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < n; ++i) {
        ++cnt[s1[i].charCodeAt() - 'a'.charCodeAt()];
    }
    let left = 0;
    let right = 0;
    const ans = [];
    while (right < m) {
        const x = s2[right].charCodeAt() - 'a'.charCodeAt();
        --cnt[x];
        // 不光是子串有的字符要统计, 子串没有的字符也要重新归0才行
        // 因为 right 遍历到了一个子串没有的字符, 说明从 left 到 right 这部分子串都不需要再遍历了
        // 一定是不能组合成子串的, 因为有多余的字符, 所以需要更新 left 到 right 的位置
        // 但是不能直接更新, 需要顺路把被抵消的字符复原才行
        while (cnt[x] < 0) {
            ++cnt[s2[left].charCodeAt() - 'a'.charCodeAt()];
            ++left;
        }
        if (right - left + 1 === n) {
            ans.push(left)
        }
        right++;
    }
    return ans;
};